//给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。 
//
// 整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3ˣ 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 27
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：n = 0
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：n = 9
//输出：true
// 
//
// 示例 4： 
//
// 
//输入：n = 45
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// -2³¹ <= n <= 2³¹ - 1 
// 
//
// 
//
// 进阶：你能不使用循环或者递归来完成本题吗？ 
//
// Related Topics 递归 数学 👍 366 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-08-13 10:16:32
 * @description 326.3 的幂
 
 */
 
public class PowerOfThree {
    public static void main(String[] args) {
    //测试代码
    PowerOfThree fun = new PowerOfThree();
    Solution solution= fun.new Solution();
        System.out.println(45%3);
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        // 观察3的幂次方
    // 3^0 = 1 3^1=101 3^2=1001 3^3=11011 3^4=100101 3^5=110111

    /*
        原理：
        1162261467 是什么？
        这是 3^19（3 的 19 次方）的值：
        3^19=1162261467
        这是 int 类型能表示的最大 3 的幂
        为什么用 % 运算？
        如果 n 是 3 的幂，那么它一定可以整除 3^19，即：
        如果 n 不是 3 的幂，就不可能整除 3^{19}。
        优点：
        O(1) 时间复杂度（只做一次取模）
        没有循环和浮点运算
        缺点：
        只能用于 int 范围（32 位），不能直接处理 long、BigInteger

        为什么 1162261467 % n == 0 能判断 n 是否是 3 的幂？

        因为 3 是质数，3^k 的因数只能是 3 的幂（如 3^0, 3^1, 3^2, ..., 3^19）。

        所以如果 1162261467 % n == 0，说明 n 是 3^k 的形式。
    * */
    public boolean isPowerOfThree1(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
    /*
        原理：
        任何数的对数都可以通过换底公式转换为其他底的对数
        换底公式：log_a(b) = log_c(b) / log_c(a)
        如果 n 是 3 的幂，那么 log_3(n) 必须是整数
        使用换底公式，我们可以计算 log_3(n) = log_10(n) / log_10(3)
        检查结果是否为整数
        优点：
        O(1) 时间复杂度（只做一次对数运算）
        没有循环
        缺点：
        可能存在浮点精度问题，尤其是对于非常大的 n
        需要使用对数函数，某些编程环境中可能不够直观
    * */
    public boolean isPowerOfThree2(int n) {
        return n> 0 && (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }

    /*
    public boolean isPowerOfFive1(int n) {
        if (n <= 0) return false;
        double log5 = Math.log(n) / Math.log(5);  // 计算 log₅(n)
        return Math.abs(log5 - Math.round(log5)) < 1e-10;  // 判断是否为整数
    }
    优点：
    显式处理了 n <= 0 的情况，避免了对数计算的非正数输入。
    使用 Math.abs 和一个小阈值（1e-10）来比较浮点数的近似相等性，可以避免浮点数精度问题。
    逻辑清晰，直接比较对数值是否接近整数。
    缺点：
    依赖一个固定的阈值（1e-10），对于非常大的 n 或非常小的 n，可能需要调整阈值。
    浮点数运算可能存在平台或实现相关的差异。


    public boolean isPowerOfThree2(int n) {
        return n > 0 && (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
    代码更简洁，直接利用 % 1 == 0 判断是否为整数。
    使用 log10 而不是自然对数 log，但这对结果没有本质影响。
    缺点：
    直接使用 % 1 == 0 对浮点数进行取模判断，可能因浮点数精度问题导致错误。例如：
    Math.log10(243) / Math.log10(3) 理论上应该是 5.0，但实际计算可能是 4.999999999999999 或 5.000000000000001，导致 % 1 不为 0。
    这种问题在较大或较小的 n 时更容易出现。
    没有显式处理浮点数的精度误差，可能在某些情况下返回错误结果。
    * */
    public boolean isPowerOfThree(int n) {
        if(n==0) return false;
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
    // 递归
    public boolean isPowerOfThree3(int n) {
        if (n < 1) return false;
        if (n == 1) return true;
        if (n % 3 != 0) return false;
        return isPowerOfThree3(n / 3);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
